The Alternating Direction Method of Multipliers (ADMM), which is a variant of an augmented Lagrangian scheme, uses partial updates for dual variables to solve a problem. The ADMM technique” alternately solves for a first variable while holding a second fixed, and solving for the second variable while holding the first variable fixed, see Boyd et al. “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, p. 1-122, 2011. Rather than iterating until convergence as in the Lagrangian-augmented problem, which is possibly complex, the ADMM performs iterations of alternating steps of updates on subsets of the variables.
The ADMM is frequently used for solving structured convex quadratic programs (QP) in applications, such as for example, compressive sensing, image processing, machine learning, distributed optimization, regularized estimation, and semi-definite programming, to name but a few.
Of particular interest to the invention is the potential application of ADMM to model predictive control (MPC) problems. MPC is a method for solving constrained dynamical systems by repeatedly solving a finite horizon optimal control formulated from system dynamics, constraints, and a user specified cost function.
For linear systems subject to linear constraints and with a quadratic cost function, the MPC finite horizon optimal control problem can be formulated as a parametric QP. At every control cycle, a specific QP is generated from the parametric quadratic program and the current values of the system state, and possibly the current reference. Then, the QP is solved, and the first part of the control input sequence is applied as control input. At the following control cycle, a new optimization problem is solved from the updated system state. MPC has been increasingly applied to systems with fast dynamics where the MPC is implemented in a low computational power embedded processors.
There are many prior art methods for determining a minimizer of the QP while satisfying linear equalities and the convex set. For example, active set methods and interior point methods are the most common iterative methods.
U.S. Pat. No. 8,600,525 discloses an active set algorithm that can be used for solving MPC generated QP problems. U.S. Pat. No. 7,328,074 further discloses a method of providing an active-set algorithm wherein an initial guess for an optimization problem is provided from the solution of a previous optimization. U.S. Publication 20060282177 discloses an interior point algorithm for solving the quadratic programs that arise in the context of model predictive control of gas turbine engines.
However, the computational effort per iteration of those methods can be prohibitive for application to large scale problems. The complexity of the operations that are performed, such as the solution of large scale linear systems, makes them infeasible for the type of computing hardware commonly used in real-time control and signal processing applications.
On the other hand, methods such as gradient methods and accelerated gradient methods cannot easily handle linear inequality constraints. Low complexity fast optimization methods have been developed for MPC.
U.S. Publication 20120281929 discloses a method for solving quadratic programs with non-negative constraints and a method to optimize such method for application to MPC.
A fast gradient algorithm is described for an application to MPC by Richter et al. “Computational Complexity Certification for Real-Time MPC With Input Constraints Based on the Fast Gradient Method,” IEEE Trans. Automat. Contr. 57(6): 1391-1403 (2012).
A Lagrangian method for MPC is described by Kögel et al., “Fast predictive control of linear, time-invariant systems using an algorithm based on the fast gradient method and augmented Lagrange multipliers,” CCA 2011: 780-785, 2011.
However, those methods are limited in the application by the types of constraints that can be handled, e.g., Richter et al., or can only handle input constraints, or need to perform division operations, e.g., in U.S. Publication 20120281929, which are time consuming in the computing hardware for MPC, or by complex iteration, e.g. Kögel et al., due to the need of achieving the solution of the Lagrangian-augmented problem, which is complex due to the presence of constraints, before updating the Lagrange multipliers, multipliers at every update.
Thus, there is a need to provide a method that can solve large scale problems with small computational complexity per iteration, good convergence when problems are feasible, and quick detection of infeasibility.